<!doctype html>
<html>
	<head>
		<title>quadtree-js 1.2.0 Performance Test</title>
		<link rel="stylesheet" type="text/css" href="style.css?v=2" />
		<meta name="viewport" content="width=device-width, initial-scale=1" />

		<!-- prism syntax highlighting (https://prismjs.com/) -->
		<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/themes/prism.min.css" integrity="sha512-tN7Ec6zAFaVSG3TpNAKtk4DOHNpSwKHxxrsiw4GHKESGPs5njn/0sMCUMl2svV4wo4BK/rCP7juYz+zx+l6oeQ==" crossorigin="anonymous" />
		<style>
			.outer {
				max-width: 800px;
			}
		</style>
	</head>
	<body>

		<div class="outer">
			
			<h1><a href="https://github.com/timohausmann/quadtree-js">quadtree-js</a> 1.2.0 <small>performance test</small></h1>

			<nav>
                <div class="nav">
                    <strong>Demos:</strong>
                    <a href="simple.html">simple</a>
                    <a href="dynamic.html">dynamic</a>
                    <a href="many.html">many to many</a>
                    <a href="test-retrieve.html">benchmark</a>
                </div>
                <div class="nav">
                    <strong>Old Benchmarks:</strong>
                    <span>benchmark 1.2</span>
                    <a href="test-10000-1.1.3.html">benchmark 1.1.3</a>
                </div>
			</nav>


			<div id="canvasContainer">
				<canvas id="canvas" width="800" height="600"></canvas>
			</div>

			<div class="ctrl">
				<div class="ctrl-left">
					Time spend for insert of <span id="cnt_total2">0</span> objects and retrieve once:<br />
					<strong><span id="cnt_time">0</span></strong>
				</div>

				<div class="ctrl-right">
					Total Objects: <span id="cnt_total">0</span><br />
					Candidates: <span id="cnt_cand">0</span> (<span id="cnt_perc">0</span>%)
				</div>
			</div>

			<p>
				Quadtree 1.2 now stores objects exclusively on leaf nodes. Objects, that overlap into multiple subnodes are now referenced in each matching subnode instead of their parent node. This drastically reduces the collision candidates. Prior to 1.2, overlapping objects were stored in parent nodes (<a href="test-10000-1.1.3.html">1.1.3 Demo</a>). 
			</p>
			<p>
				Because objects may now be present in multiple nodes, nodes will split rather soon (depending on the max_objects value, default&nbsp;=&nbsp;10&nbsp;objects per node).
			</p>

			<p>Heart of the test code:</p>

			<pre><code class="language-javascript">var amount = 10000;
var myObjects = [];
for(var i=0; i&lt;amount;i++) {
	myObjects.push({
	x: randMinMax(0, 800-maxObjectSize),
	y: randMinMax(0, 600-maxObjectSize),
	width: randMinMax(4, maxObjectSize),
	height: randMinMax(4, maxObjectSize)
	});
}

//time measure starts here
var start = window.performance.now();

var myTree = new Quadtree({
	x: 0,
	y: 0,
	width: 800,
	height: 600
}, 10, 4);

for(var i=0; i&lt;amount;i++) {
  myOldTree.insert(myObjects[i]);
}
var candidates = myOldTree.retrieve(myCursor);

//time measure ends here
var end = window.performance.now();
var time = end - start;</code></pre>

			<p>
				To see the full example code please check the page source or 
				<a href="https://github.com/timohausmann/quadtree-js/tree/master/docs" target="_blank" rel="noopener noreferrer">visit GitHub</a>.
			</p>
		</div>

		<!-- github corner (https://github.com/tholman/github-corners) -->
		<a href="https://github.com/timohausmann/quadtree-js" class="github-corner" aria-label="View source on GitHub"
			target="_blank" rel="noopener noreferrer">
			<svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true">
				<path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path>
			</svg>
		</a>

		<!-- prism syntax highlighting -->
		<script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>

		<!-- quadtree lib and script -->
		<script src="./quadtree.min.js"></script>
		<!-- CDN alternative: -->
		<!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script> -->
		<script>

			//---- SETUP
			var amount = 10000;
			var max_objects = 10;
			var max_levels = 4;
			var width = 800;
			var height = 600;
			var maxObjectSize = 64;

			var randMinMax = function(min, max, round) {
				var val = min + (Math.random() * (max - min));	
				if(round) val = Math.round(val);	
				return val;
			};

			var myCursor = {
				x : randMinMax(120,width-120),
				y : randMinMax(120,height-120),
				width : 32,
				height : 32
			};

			var myObjects = [];
			for(var i=0; i<amount;i++) {
				myObjects.push({
				  x: randMinMax(0, width-maxObjectSize),
				  y: randMinMax(0, height-maxObjectSize),
				  width: randMinMax(4, maxObjectSize),
				  height: randMinMax(4, maxObjectSize)
				});
			}

			console.log('Quadtree 1.2 with', amount, 'objects on leaf nodes only');


			//---- TEST
			var start = window.performance.now();

			var myTree = new Quadtree({
				x: 0,
				y: 0,
				width: width,
			    height: height
			}, max_objects, max_levels);

			for(var i=0; i<amount;i++) {
				myTree.insert(myObjects[i]);
			}

			var candidates = myTree.retrieve(myCursor);

			var end = window.performance.now();
			var time = end - start;

			console.log('Found', candidates.length, 'candidates in', time, 'ms');


			//---- DRAW RESULT
			var ctx = document.getElementById('canvas').getContext('2d');

			//updateTotal
			document.querySelector('#cnt_total').innerHTML = myObjects.length;
			document.querySelector('#cnt_total2').innerHTML = myObjects.length;
			document.querySelector('#cnt_cand').innerHTML = candidates.length;
			document.querySelector('#cnt_perc').innerHTML = Math.round((candidates.length/myObjects.length)*100);
			document.querySelector('#cnt_time').innerHTML = Math.round(time) + 'ms';

			//flag retrieved objects
			for(i=0;i<candidates.length;i=i+1) {
				candidates[ i ].check = true;
			}

			/*
			 * draw Quadtree nodes
			 */
			var drawQuadtree = function(node) {

				var bounds = node.bounds;
			
				//no subnodes? draw the current node
				if(node.nodes.length === 0) {
					ctx.strokeStyle = 'rgba(255,0,0,0.5)';
					ctx.strokeRect(bounds.x, bounds.y, bounds.width, bounds.height);
					
				//has subnodes? drawQuadtree them!
				} else {
					for(var i=0;i<node.nodes.length;i=i+1) {
						drawQuadtree(node.nodes[ i ]);
					}
				}
			};
			
			/*
			 * draw all objects
			 */
			var drawObjects = function() {
				
				var obj;
				
				for(var i=0;i<myObjects.length;i=i+1) {
					
					obj = myObjects[ i ];
					
					if(obj.check) {
						ctx.fillStyle = 'rgba(48,255,48,0.5)';
						ctx.fillRect(obj.x, obj.y, obj.width, obj.height);
					} else {
						ctx.strokeStyle = 'rgba(255,255,255,0.5)';
						ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
					}
				}
			};

			drawObjects();
			drawQuadtree(myTree);

			//draw retrieve area
			ctx.strokeStyle = 'blue';
			ctx.lineWidth = 2;
			ctx.fillStyle = 'rgba(255,255,255,0.5)';
			ctx.fillRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);
			ctx.strokeRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);

		</script>

	</body>
</html>
